/**
 * @param {number[][]} pairs
 * @return {number[][]}
 */
 var validArrangement = function(pairs) {
  let head = new Map(), cnt = new Map()
  for(let [x, y] of pairs){
    if(!head.has(x)) head.set(x, [])
    head.get(x).push(y)
    cnt.set(x, (cnt.get(x) || 0) + 1)
    cnt.set(y, (cnt.get(y) || 0) + 1)
  }
  let ans = []
  const used = new Set()
  const dfs = (x, y, path) => {
    if(!head.has(y) || path.length === pairs.length){
      if(path.length === pairs.length){
        ans = path
      }
      return
    }
    for(let y1 of head.get(y)){
      if(!used.has([y,y1].toString())){
        used.add([y,y1].toString())
        dfs(y, y1, [...path, [y,y1]])
        used.delete([y,y1].toString())
      }
    }
  }
  let start = pairs[0][0]
  for(let [k, v] of cnt.entries()){
    if(v % 2 !== 0 && head.has(k)){
      start = k
      break
    }
  }
  let startP = head.get(start)
  used.add(startP.toString())
  dfs(...startP, [startP])
  return ans
};

/**

 var validArrangement = function(pairs) {
  let head = new Map(), cnt = new Map()
  for(let [x, y] of pairs){
    if(!head.has(x)) head.set(x, [])
    head.get(x).push(y)
    cnt.set(x, (cnt.get(x) || 0) + 1)
    cnt.set(y, (cnt.get(y) || 0) + 1)
  }
  let start = pairs[0][0]
  for(let [k, v] of cnt.entries()){
    if(v % 2 !== 0 && head.has(k)){
      start = k
      break
    }
  }
  const used = new Set()
  let q = [start]
  while(q.length){
    console.log(q)
    let temp = []
    for(let i = 0, len = q.length; i<len; i++){
      let cur = q.pop()
      if(head.has(cur)){
        for(let next of head.get(cur)){
          if(!used.has([cur, next].toString())){
            temp.push(next)
            used.add([cur, next].toString())
          }
        }
      }
    }
    q = temp
  }
  return []
};
**/